#include<stdio.h>
#include<stdlib.h>
struct node{
	int data;
	struct node *left;
	struct node *right;
	struct node *parent;
};
typedef struct node node;
node *head=NULL;
node* createNode(int i){
	node *temp=(node*)malloc(sizeof(node));
	temp->data=i;
	temp->left=NULL;
	temp->right=NULL;
	temp->parent=NULL;
	return temp;
}
int height(node *temp){
	if(temp==NULL)return 0;
	else{
		int h1=height(temp->left);
		int h2=height(temp->right);
		return h1>h2?h1+1:h2+1;
	}
}
void insert(int i){
	node *temp=createNode(i);
	if(head==NULL)head=temp;
	else{
		node *ptr=head;
		while(ptr->left!=NULL && ptr->right!=NULL){
			int h1=height(ptr->left);
			int h2=height(ptr->right);
			ptr=h1>h2?ptr->right:ptr->left;
		}
		temp->parent=ptr;
		if(ptr->left==NULL){
			ptr->left=temp;
		}
		else ptr->right=temp;
	}
}
int inorderSuccesor(node* temp);
void display(node *temp){
	if(temp==NULL)return;
	display(temp->left);
	printf("%d",temp->data);
	printf ("%d \n",inorderSuccesor(temp));
	display(temp->right);
}

int first(node *temp){
	while(temp->left!=NULL){
		temp=temp->left;
	}
	return temp->data;
}
int inorderSuccesor(node *temp){
	printf("in order ");
	if(temp==NULL)return;
	if(temp->right!=NULL){
		return first(temp->right);
	}
	node *parent=temp->parent;
	if(parent->left==temp){
		return parent->data;
	}
	else if(parent->right==temp){	
		node* parent2=parent->parent;		
		if(parent2==NULL){
			return -1;
		}
		else return inorderSuccesor(parent2);
	}
}
void main(){
	insert(1);
	insert(2);
	insert(3);
	display(head);
}

